The goal of timing-driven layout, such as floorplanning, placement, wiring, etc., is to perform the layout design process such that the design satisfies the particular timing constraints specified by the designer. In the most general case, the timing constraint information is specified to the timing-driven layout tools in the form of arrival times for signals at the inputs of the design, and required arrival times for signals at the outputs of the design.
Timing-driven design tools generally deal with timing constraints in one of three ways or some variation thereof, namely, basing the design on path delay, net weight, or net delay. A net is an electrical connection of physical pins and/or logical input/output ports of electronic components.
Path delay based tools consider timing constraints on specified timing paths in the design, and perform the design process so as to satisfy these constraints. The constraints are generally in the form of maximum and/or minimum resistance-capacitance (RC) delay through a path. Theoretically, a timing constraint could be specified for every input-output path in the design. However, the number of such paths increases exponentially with the size of the design and, in practice, only a limited subset of paths can be effectively processed by conventional timing-driven tools. Thus, for large designs, it is impractical to monitor all paths in a design during the design process. In this regard, the cost can be reduced by monitoring a subgraph of the design containing several paths rather than monitoring the individual paths.
Net weight based methods consider weight factors for the nets. These weight factors indicate the relative importance of each net with respect to timing. Net weight based methods attempt to shorten nets having higher weights, thus reducing their delay, at the expense of other nets with lower weights. However, net weight based methods cannot guarantee meeting the overall timing constraints and, generally, must be run several times, adjusting the net weights with each run, in order to converge on the required timing for a particular design.
Net delay based tools consider targets, namely, resistance (R), capacitance (C) and resistance-capacitance (RC), on individual nets in the design and perform the design process so as to satisfy these targets. Typically, the individual net targets are generated based on the overall design constraints such that if every net target is met, the overall design will meet the timing goals. Net delay based approaches are able to monitor all nets in a design during the design process with relatively low computation cost. However, the effectiveness of the tool hinges on how the net targets are generated.
Existing target generation approaches apportion the delay specified on a path, which consists of several nets, as individual RC delay targets on the constituent nets. Generally, conventional target generation approaches follow the basic principles of target generation, but each may differ with respect to variations on the set of timing paths generated, and the way in which the delay on a path is apportioned to its constituent nets. See, for example, W. K. Luk, "A Fast Physical Constraint Generator for Timing Driven Layout", 28th ACM/IEEE Design Automation Conference, Paper 37.3, June 1991, pp. 626-631 ("the Luk paper"); and H. Youssef and E. Shragowitz, "Timing Constraints for Correct Performance", Proc. ICCAD, November 1990, pp. 24-27 ("the Youssef and Shragowitz paper").
In accordance with conventional target generation approaches, the input is the timing constraints on the design, and the output is the targets on the nets. Typically, the procedure begins by setting all initial targets on all nets to zero, and then proceeding with the following steps:
1. Run timing analysis on the logic network. This step takes into account the targets generated in the previous iteration of the repeat loop, and generates (i) a set of timing paths (each consisting of a sequence of timing nodes), and (ii) a slack value for each path. Slack is the amount of delay that can be added to a path without affecting the performance of the design;
2. Apportion the slack values on the paths to the nets contained in these paths. This step is carried out differently in different target generation approaches. In general, this step takes into account information such as existing targets on the nets, loading on the nets due to the cells they are connected to, the sensitivity of the net delays to changes in capacitance and resistance, etc.; and
3. Repeat steps 1 and 2 until all path slacks are zero or sufficiently near zero. In practice there may be an upper bound on the number of iterations after which the algorithm must exit. The targets on the nets thus generated are then passed on to placement/wiring programs.
Explained in another way, in essence, conventional target generation processes transform timing constraints on a design into timing constraints on the nets within the design, where the cells that are connected together by the nets are fixed predesigned entities (library cells or standard cells) that have known delays. This is illustrated in FIG. 1 which shows one critical path through a chip 10 from an input pin P1 to an output pin P2. The path is made up of six nets, n1-n6, and five standard cells, c1-c5. Assuming that there is a positive slack S on this path as determined by timing analysis, i.e., S units of delay can be added to this path without affecting the performance of the design, the target generation algorithms apportion the slack value S among the nets n1-n6, and accordingly modify the R, C and RC targets on these nets to reflect this apportionment. Note that this is a simple example with a single critical timing path. In general, there are many critical timing paths that intersect each other, and the targets assigned to a given net must be based on the slacks on all the timing paths to which it belongs.
Thus, conventional approaches for target generation work with "flat" designs in which the cells that the paths pass through are predesigned entities with fixed delays. However, in so-called multilevel hierarchical circuit designs, this condition may not hold since the cells themselves are made up of hierarchical entities whose internals have not yet been designed. Generally, a multilevel hierarchical circuit design refers to an electronic design whose representation has a containment hierarchy, i.e., the entire design is made up of a cell, which in turn contains child cells connected to each other by nets. Each cell is either a standard cell, which means that it is a predesigned cell taken from a standard cell library, or a macro cell, which means it contains one or more child cells. The children of macro cells may be standard cells or themselves macro cells. The current hierachy level refers to the particular level of design hierarchy at which the physical design is being carried out at a given time.
Referring to FIG. 2, in a multilevel hierarchical circuit design, there may be several levels of hierarchy between the top level entity of a design hierarchy, for example, chip 12, and the predesigned leaf level entities, for example, standard or library cells c6-c9, for which delay models are available. Thus, the top level entity or chip 12 of the hierarchy can be made up of macro cells, m1 and m2, that have not yet been designed. The lower-level cells c6-c9 (which may be standard cells or macro cells themselves) within the macro cells m1,m2 have not been placed and wired, and hence there are no fixed timing models available for the macro cells m1,m2. In order to use conventional techniques of target generation on the design of FIG. 2, the hierarchy would have to be "flattened", i.e., the boundaries of the hierarchical macro cells m1,m2 would have to be removed. Target generation could then be carried out on the flattened design to derive targets on the nets.
Existing target generation approaches described above cannot be used on multilevel hierarchical circuit design for several reasons, as follows:
1. Conventional target generation approaches assume that each cell in the design is a predesigned standard cell with fixed timing properties;
2. Even if target generation was carried out using conventional target generation on the flattened design, i.e., with the macro cell boundaries removed, the resulting net targets would not be directly useful. Specifically, the target assigned to any wire that crosses a macro cell boundary would still have to be apportioned to the two subnets, one outside and one inside the macro cell, because only the former is visible to a hierarchical floorplanner when it is working on the upper level of the hierarchy. For example, nets n7 and n8 in the hierarchical design illustrated in FIG. 2.
3. The floorplanning process being utilized would generally result in a layout in which nets within a macro cell have lower average length than nets crossing macro boundaries. Existing target generation approaches working on the "flattened" design would not take advantage of this to proportionately distribute wire delays.
Another disadvantage is that such flattening defeats the purpose of hierarchical design and requires the whole flattened design to be processed at once, which requires prohibitive amounts of memory and computation time for large designs. Further, in using this flattening approach, all nets are given equal weightage in "apportioning" delays among them, thus "local" nets, within macros such as m1, that have a lower average length cannot be distinguished from "global" nets across the whole chip that have a higher average length.
Accordingly, an improved target generation approach is required, particularly for multilevel hierarchical circuit designs.